package com.yiguang.algorithm.dp;

/*
 * 105. 岛屿的最大面积
 */
public class IslandMaxArea {
	
	public int getIslandGirth(int[][] grid) {
		int result = 0;
		int rowLength = grid.length;
		int colLength = grid[0].length;
		for(int i=0; i<rowLength; i++) {
			for(int j=0; j<colLength; j++) {
				int current = grid[i][j];
				if(current==1) {
					grid[i][j]=0;
					int currentResult = dfs(grid, i, j, rowLength, colLength, 1);
					if(currentResult>result) {
						result = currentResult;
					}
				}
			}
		}
		return result;
	}
	
	public int dfs(int[][] grid, int row, int column, int rowLength, int colLength, int currentResult) {
		// top
		if(row-1>=0 && grid[row-1][column]==1) {
			grid[row-1][column]=0;
			currentResult = dfs(grid, row-1, column, rowLength, colLength, currentResult+1);
		}
		// right
		if(column+1<colLength && grid[row][column+1]==1) {
			grid[row][column+1]=0;
			currentResult = dfs(grid, row, column+1, rowLength, colLength, currentResult+1);
		}
		// bottom
		if(row+1<rowLength && grid[row+1][column]==1) {
			grid[row+1][column]=0;
			currentResult = dfs(grid, row+1, column, rowLength, colLength, currentResult+1);
		}
		return currentResult;
	}
	
	public static void main(String[] args) {
		/*
		[0,1,0,0]3
		[1,1,1,0]
		[0,1,0,0]
		[1,1,0,0]
		
		[
		[0,1,0,0],3
		[1,1,1,0],6
		[0,1,0,0],2
		[1,1,0,0]5
		]
		*/ 
		int[][] grid = {{0,1,0,0},{1,1,1,0},{0,1,0,0},{1,1,0,0}};
		IslandMaxArea islandMaxArea = new IslandMaxArea();
		islandMaxArea.getIslandGirth(grid);
	}
	
}
